package org.duiduo;

import com.alibaba.fastjson.JSON;

/**
 * 两数相加
 *
 * @author liangze
 * @date 2023/7/3 16:28
 */
public class Chap2Code {

    public static void main(String[] args) {
        ListNode l1 = new ListNode(4);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(2);

        ListNode l2 = new ListNode(4);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(2);

        // [2,3,4] [2,3,4] (逆序)  [8,6,4]  432+432=864
        ListNode listNode = addTwoNumbers(l1, l2);
        System.out.println(listNode.val + "<=>" + listNode.next.val + "<=>" + listNode.next.next.val);
    }

    private static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 创建一个虚拟头节点【不要动他】
        ListNode pre = new ListNode(0);
        // 创建一个指针指向头节点【动他】
        ListNode cur = pre;
        // 定义一个变量表示进位
        int carry = 0;

        // 遍历两个链表，直到都为空
        while(l1 != null || l2 != null) {
            // 取出两个链表的当前值，如果为空则为0【① 取出加数 被加数】
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            // 计算两个值的和，加上进位【② 先求和：加数+被加数+进位】
            int sum = x + y + carry;

            // 更新进位，如果和大于等于10，则进位为1，否则为0【③ 再更新进位carry，只有两个取值1,0】
            carry = sum / 10;
            sum = sum % 10;
            // 创建一个新的节点，存储和的个位数【④ 最后节点存入结果（链表）sum的个位】
            cur.next = new ListNode(sum);

            //            =========  循环指针更新    =============
            // 移动指针到下一个节点
            cur = cur.next;
            // 如果链表不为空，则移动到下一个节点
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        // 如果最后还有进位，则在末尾添加一个节点【把多的那个进位 存上】
        if (carry > 0) {
            cur.next = new ListNode(carry);
        }

        // 返回虚拟头节点的下一个节点，即真正的头节点
        return pre.next;
    }


    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

}
